import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/6 8:36
 * @description 动态规划，dp[i][j]为走到下标为（i，j）位置需要的路径数量，因为只能向下或向右走一步，边界：dp[0][0] = 1;
 * dp[i][0] = 1; dp[0][j] = 1
 * 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
 *
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++)  {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
